package com.ryujung.binary_tree.leetCode_687;

/*
Given a binary tree, find the length of the longest path where each node in the path
 has the same value. This path may or may not pass through the root.

The length of path between two nodes is represented by the number of edges between them.

Example 1:
Input:
              5
             / \
            4   5
           / \   \
          1   1   5
Output: 2


Example 2:
Input:
              1
             / \
            4   5
           / \   \
          4   4   5
Output: 2

Note: The given binary tree has not more than 10000 nodes. 
The height of the tree is not more than 1000.
*/

//Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

/**
 * 递归调用，深度优先算法 Note：最长的链可能是一个子节点的子树也可能是某条过根节点的链, 
 * 要在两种情况中选出最大的一个。
 * 
 * 具体实现： 
 * 1.设计一个递归函数 
 * 
 * 2.递归函数的返回值 
 * 21. 我们希望这个函数能够得到：从 node 节点开始，
 * 向下出发，最长的同值路径长度 
 * 22.因为路径的一个方向是通向 node 的父节点，所以另一个方向只能从 node 的左或右节点中选择至多一个
 * 
 * 递归函数的出口 
 * 31. 如果 node 为空，返回 0
 * 
 * 递归函数的逻辑 
 * 41. 当我们递归调用 node->left 和 node->right 时，
 * 就可以得到左/右子树与其数值相同节点的长度 
 * 42.只需要判断左/右子树的数值与根节点的数值是否相同，不相同的话就舍弃，
 * 相同的话长度就加一 
 * 43. 那么与 node 值相同的路径长度就是左/右两条路中较长的
 * 
 * 递归函数只能取得 node 的同值路径长度，这里还有一些其他情况需要考虑 
 * 51.如果最长的路径是由一个其他数值的子节点开始向下出发的情况，在递归中间因为数值不同被舍弃了 
 * 52. 是由一个子节点，向左右两个方向同时向下出发的情况（情况1）
 * 
 * 在递归函数的参数中使用一个引用变量，记录全局最大值 
 * 61. 当计算出一个节点的返回值时，将以这个节点，连接左右两边的路径长度，更新到全局最大值 
 * 62.然后再返回这个全局最大值包含了以上所有情况，就是题目的答案
 */
class Solution {
    int res = 0;
    public int longestUnivaluePath(TreeNode root) {
        if(root!=null)throughRootPath(root);
        return res;
    }

    //因为要递归调用,所以需要返回值
    private int throughRootPath(TreeNode root) {
        if(root==null)return 0;

        int left = throughRootPath(root.left);
        int right = throughRootPath(root.right);

        //如果之前的值与当前节点不相同,则抛弃之前递归的结果
        left = root.left!=null && root.left.val==root.val?left+1:0;
        right = root.right!=null && root.right.val==root.val?right+1:0;

        //记录不断变化的当前节点下的长度和已记录的最大长度,取更大的值
        res = Math.max(res, left + right);
        
        return Math.max(left,right);
    }
    

}
/*
    int res = 0;
    public int longestUnivaluePath(TreeNode root) {
        helper(root);
        return res;
    }
    
    int helper(TreeNode root){
        if(root == null) return 0;
        
        int left = helper(root.left);
        int right = helper(root.right);
        
        left = (root.left != null && root.left.val == root.val) ? left + 1 : 0;
        right = (root.right != null && root.right.val == root.val) ? right + 1 : 0;
        
        res = Math.max(res, left + right);
        return Math.max(left, right);
    }
*/